import java.util.Arrays;
import java.util.Random;

public class ImProveQuickSort {
    public static void main(String[] args) {
        int[] array = {1,5,2,3,4,6,9,8,7,10,11,12,13};
        imProvequickSort(array,0,array.length - 1);
        System.out.println(Arrays.toString(array));
    }
    //对存在大量重复数据进行的优化快速排序
    public static void imProvequickSort(int[] elem,int start,int end){
        if(start >= end){
            return;
        }
        int benchmark = partiotion(elem,start,end);
        //优化重复数字
        int leftPivot = benchmark - 1;
        int rightPivot = benchmark + 1;
        //优化重复元素
        while(leftPivot > start && elem[leftPivot] == elem[benchmark]){
            leftPivot --;
        }
        while(rightPivot < end && elem[rightPivot] == elem[benchmark]){
            rightPivot++;
        }
        //通过递归再次在基准值左右两边再次找基准
        //找左边基准值
        imProvequickSort(elem,start,leftPivot);
        //找右边基准值
        imProvequickSort(elem,rightPivot,end);
    }
    private static final Random random = new Random();
    public static int partiotion(int[] elem,int left,int right){
        //以随机下标作为基准值
        int RandomIndex = left + random.nextInt(right - left + 1);
        swap(elem,left,RandomIndex);
        int tmp = elem[left];
        int i = left;
        while (left < right){
            while (left < right && elem[right] >= tmp){
                right--;
            }
            //elem[left] = elem[right];
            while (left < right && elem[left] <= tmp){
                left++;
            }
            //elem[right] = elem[left];
            swap(elem,left,right);
        }
        //将基准值放到基准下标
        swap(elem,left,i);
        //当left等于right的时候，基准值下标找到了
        return left;
    }
    public static void swap(int elem[],int i, int j){
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }
}
